1. Field of the Invention
This invention relates to tracking moving objects. More specifically, it relates to using past location and future destination information to compute an expected trajectory of a moving object.
2. Description of Related Art
Common devices such as cell phones, personal digital assistants, laptops and the like, can be equipped to provide location information. These devices are generally also equipped for wireless transmission of data. The device""s location is updated using positioning technologies. Examples of positioning technologies include 1) global positioning systems, commonly called GPS, 2) network based positioning, which computes the location of a device by triangulation of its wireless signal between transmission towers, 3) a fixed sensor in the environment that identifies the moving object, and 4) cell-identification, which identifies the cell in which the moving object is located.
The devices can be carried by, or mounted on, moving objects such as vehicles, aircraft, vessels or pedestrians. The location of the small device corresponds directly to the location of the larger device. Using the wireless capability of the devices, the location is transmitted to a central system for tracking the motion of the moving object. The central system typically stores the location information of the object, and provides a method for displaying that information to a user.
Location information management involves tracking the moving object, modeling its location (for example, by representing it in a server) and retrieving data. Existing systems perform location management by receiving a time-location point. This point is typically of the form (x,y,t), and it is generated periodically by the device and transmitted to the location management system. This may occur, for example, once every 10 minutes. The point indicates the object""s coordinates (x,y) at time t.
The location management system is typically a database managed by a Database Management System (DBMS). The database provides interfaces for receiving the location information and for displaying the information to users. When the DBMS receives a location point, it stores it in the database. The DBMS supports Structured Query Language (SQL), which can be used to access and query the information stored in the database. In these systems, if the exact current location of a moving object is required at a particular time, then the object is contacted, its location is retrieved, and the result is stored in the database. The method is called point-location management, and it has several disadvantages.
First, point-location management does not allow interpolation or extrapolation of data. In point-location management, the system only knows the time-location points stored in its database. It cannot interpolate the past position of a moving object, for example at time X, using data sets subsequent to that time. Also, it cannot extrapolate a future location of the moving object from past data sets. In addition, the point-location management system has difficulty determining the current location of all its moving objects. Since the system does not support extrapolation, to find the current location of its moving objects the system must simultaneously poll each moving object. This causes an undesirable bandwidth spike on the network as the system attempts to contact each object. Objects disconnected from the network are not polled, and their location will not be known.
A second disadvantage is that point-location leads to a tradeoff between precision and resources. Obtaining an accurate picture of moving objects"" precise locations requires frequent location updates. This consumes limited system resources such as bandwidth and processing power. When these resources are not taxed by frequent location updates, the location information quickly becomes dated and, therefore, imprecise.
A third problem of point-location management is that it leads to cumbersome and inefficient software development. This creates several problems for developing location based service applications. Existing DBMS""s are not well equipped to handle continuously changing data, such as the location of moving objects, because in existing databases data is assumed to be constant unless it is explicitly modified. Location based service applications also need to manage space and time information; however, SQL is not designed or optimized for these types of when/where queries. For example, the query xe2x80x9cretrieve the vehicles that are inside the region R always between 4 pm and 5 pmxe2x80x9d would be extremely difficult to express in SQL.
Additionally, moving object locations are inherently imprecise because the database location of the object (i.e., the object location stored in the database) cannot always be identical to the actual location of the object. This inherent uncertainty impacts database modeling, querying and indexing. For example, there can be two different kinds of answers to queries. These are the set of object that xe2x80x9cmayxe2x80x9d satisfy the query, and the set of objects that xe2x80x9cmustxe2x80x9d satisfy the query. These queries aren""t supported in current point-location DBMS""s. Furthermore, existing DBMS""s have no parameters to account for varying levels of uncertainty, such as was that truck within 100 inches, 100 feet, 100 yards, or 100 miles of an intermediate point calculated.
Therefore, there exists a need to more accurately represent the travel paths of moving object and to predict the future movement of objects. There further exists a need to allow complex queries regarding the past and future locations of moving objects.
A database system receives location information from a moving object. The object may be a vehicle, aircraft, pedestrian or some other object. Using the object""s destination and a past known location, the system estimates the object""s current location. The estimation is done by constructing and maintaining a trajectory of the moving object. Using the trajectory, the system can also estimate past or future locations.
The moving object periodically transmits its location to a moving object database (MOD). The moving object database receives and stores the time and location of the moving object. An electronic map, which contains travel time and distances for permissible travel paths, is also stored in the database. Destinations of the moving object are inputted into the system. Using the electronic map, the system finds the shortest path from the current location of the moving object to its destination. The system then converts the path into a trajectory.
The trajectory may be maintained by updating it to account for location updates of the moving object. It may also be updated to account for changes in travel conditions. These may be received, for instance, from websites that provide real-time traffic conditions. A traffic incident model identifies trajectories affected by traffic incidents, and it provides a method of updating a trajectory to account for delays caused by traffic incidents.
The trajectory may be sent from the database to the moving object. Using the trajectory, the moving object may extrapolate its anticipated position from the trajectory. The moving object compares its anticipated position to its actual position and provides an updated location to the moving object database when the difference between the two positions exceeds a specified threshold. The moving object database then computes a new trajectory using the new location information, and it sends this information back to the moving object.
The system also defines a set of operators that can be used to query trajectory data in the moving object database. For example, a query might find the objects that will be within 1 mile of a certain location at a given time. The operators may also be used to notify a user when specific condition occurs. For example, a user may be notified when an object is expected to be late by more than one hour. The operators can be incorporated into the traditional SQL query language, which has been widely adopted by many commercial database systems. The new operators allow for the development of complex spatial and temporal applications.
These as well as other aspects and advantages of the present invention will become apparent to those of ordinary skill in the art by reading the following detailed description, with appropriate reference to the accompanying drawings.